package leetcode_1_20;

import utils.ListNode;

public class addTwoNumbers_2 {
    /**
     * 2.1，两数相加
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        //存储结果的节点
        ListNode root=new ListNode(0);
        //用来操作的节点
        ListNode result=root;
        //每位相加后的进位数
        int remainder;
        //1，对最低位先计算
        if( (l1.val+l2.val) < 10 ) {
            result.val = l1.val + l2.val;
            remainder = 0;
        }
        else {
            result.val = l1.val + l2.val - 10;
            remainder=1;
            if(l1.next==null && l2.next==null) {
                result.next=new ListNode();
                result.next.val=1;
                return root;
            }
        }
        //2，若L1和L2下一位都为空，则停止
        while( l1.next!=null || l2.next!=null ){
            result.next=new ListNode();
            //3.1，若L2的下一位为空，则只对 l1 进行运算 并判断是否需要进位
            if ( l2.next==null ){
                if (l1.next.val+remainder<10) {
                    result.next.val = l1.next.val + remainder;
                    //重置进位数
                    remainder=0;
                }
                else {
                    //只有9+进位数位为1的情况，所以该位变为0
                    result.next= new ListNode(0);
                    //重置进位数
                    remainder=1;
                    //如果l1 下一位为空。计算结束
                    if(l1.next.next==null) {
                        result.next.next=new ListNode(1);
                        return root;
                    }
                }
                //分别进行进位
                result=result.next;
                l1=l1.next;
            }
            //3.2,  若L1的下一位为空，则只对 l2 进行运算 并判断是否需要进位
            else if ( l1.next==null ){
                if (l2.next.val+remainder<10) {
                    result.next.val = l2.next.val + remainder;
                    //重置进位数
                    remainder=0;
                }
                else {
                    //只有9+进位数位为1的情况，所以该位变为0
                    result.next= new ListNode(0);
                    //重置进位数
                    remainder=1;

                    //如果l2 下一位为空。计算结束
                    if(l2.next.next==null) {
                        result.next.next=new ListNode(1);
                        return root;
                    }
                }
                //分别进行进位
                result=result.next;
                l2=l2.next;
            }
            //3.3 ,  若都不为空
            else {
                if(l2.next.val+l1.next.val+remainder<10){
                    result.next.val =l2.next.val+l1.next.val+remainder;
                    //各自进位
                    result=result.next;
                    remainder=0;
                    l1=l1.next;
                    l2=l2.next;
                }else {
                    //若大于10
                    result.next.val=l2.next.val+l1.next.val+remainder-10;
                    remainder=1;
                    result=result.next;
                    l1=l1.next;
                    l2=l2.next;
                    if(l1.next==null && l2.next==null) {
                        result.next=new ListNode(1);
                        return root;
                    }
                }
            }
        }
        return root;
    }

    /**
     * 2.2，采取另一种方法，代码更为简洁，但占用内存很大
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        ListNode root=new ListNode(0);
        //用来操作的节点
        ListNode result=root;
        int sum=0; //相加和
        //每位相加后的进位数
        int remainder=0;
        while(l1!=null || l2!=null || remainder!=0){
            //先判断该位相加之和
            sum= ( l1!=null ? l1.val : 0 ) + ( l2 != null ? l2.val: 0 ) + remainder;
            //忽略首节点
            result.next = new ListNode(sum % 10);
            //判断下一节点是否需要加 1 , 三目运算符比sum/10 所占内存更小
            remainder = sum > 9 ? 1 : 0 ;
            //进位
            result=result.next;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        return root.next;
    }

}
